package main.leetcode.offer.secondround.from03to50;

/** 16.数值的整数次方 */
public class ex16 {
    public static void main(String[] args) {
        System.out.println(new ex16().myPow(2, 10));
        System.out.println(new ex16().myPow(2, -2));
        System.out.println(new ex16().myPow(2.1, 3));
        System.out.println(new ex16().myPow(0.00001, 2147483647));
    }

    //    public double myPow(double x, int n) {
    //        if (n == 0) {
    //            return 1;
    //        }
    //        boolean flag = n < 0;
    //        n = flag ? -n : n;
    //        long time;
    //        double tmp = x;
    //        for (time = 2; time <= n; time *= 2) {
    //            x *= x;
    //        }
    //        time /= 2;
    //        while (time++ < n) {
    //            x *= tmp;
    //        }
    //        return flag ? 1 / x : x;
    //    }

    //    public double myPow(double x, int n) {
    //        // 给出的 n 可以取到 -2147483648−2147483648（整型负数的最小值），
    //        // 因此，在编码的时候，需要将 n 转换成 long 类型。
    //        long m = n;
    //        if (n < 0) {
    //            x = 1 / x;
    //            m = -m;
    //        }
    //        double res = 1;
    //        while (m > 0) {
    //            if ((m & 1) == 1) {
    //                res *= x;
    //            }
    //            x *= x;
    //            // 右移相当于除以2，所以时间复杂度是O(logn)
    //            m >>= 1;
    //        }
    //        return res;
    //    }

    public double myPow(double x, int n) {
        // 给出的 n 可以取到 -2147483648−2147483648（整型负数的最小值），
        // 因此，在编码的时候，需要将 n 转换成 long 类型。
        if (n < 0) {
            return 1 / myPow(x, -(long) n);
        }
        return myPow(x, (long) n);
    }

    public double myPow(double x, long n) {
        if (n == 0 || x == 1) {
            return 1;
        }
        // 按奇偶性来分治
        if ((n & 1) == 0) {
            double tmp = myPow(x, n >> 1);
            return tmp * tmp;
        } else {
            double tmp = myPow(x, (n - 1) >> 1);
            return tmp * tmp * x;
        }
    }
}
